package restore_ip_addresses

import "strconv"

var ans []string

func restoreIpAddresses(s string) []string {
	ans = make([]string, 0)
	helper(s, 0, 0, "", "")
	return ans
}

func helper(s string, index int, segIndex int, seg string, ip string) {
	if index == len(s) && segIndex == 3 && isValidSeg(seg) {
		ans = append(ans, ip+seg)
		return
	}
	if index < len(s) && segIndex <= 3 {
		ch := s[index]
		if isValidSeg(seg + string(ch)) {
			helper(s, index+1, segIndex, seg+string(ch), ip)
		}
		if len(seg) > 0 && segIndex < 3 {
			helper(s, index+1, segIndex+1, string(ch), ip+seg+".")
		}
	}
}

func isValidSeg(seg string) bool {
	i, _ := strconv.Atoi(seg)
	return i <= 255 && (seg == "0" || seg[0] != '0')
}
